#include<iostream>
using namespace std;
//定义结点类
class ListNode {
public:
    int val; //数据域
    ListNode* next; //指针域
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//定义链表类
class LinkList {
private:
    
public:
    ListNode* head; //头结点
    LinkList() { //构造函数
        head = nullptr;
    }
    ~LinkList() { //析构函数，释放内存
        ListNode* p = head;
        while (p) {
            ListNode* q = p->next;
            delete p;
            p = q;
        }
    }
    void insert(int d, int pos) { //在指定位置插入结点
        ListNode* p = head;
        ListNode* q = new ListNode(d); //创建新结点
        if (pos == 0) { //在头部插入
            q->next = head;
            head = q;
        } else { //在其他位置插入
            for (int i = 0; i < pos - 1 && p; i++) {
                p = p->next; //找到前驱结点
            }
            if (p) { //如果前驱结点存在
                q->next = p->next; //将新结点的指针域指向后继结点
                p->next = q; //将前驱结点的指针域指向新结点
            } else { //如果前驱结点不存在，说明位置不合法
                cout << "Invalid position!" << endl;
                delete q; //释放新结点的内存
            }
        }
    }
    void remove(int pos) { //删除指定位置的结点
        ListNode* p = head;
        if (pos == 0) { //删除头结点
            if (head) { //如果头结点存在
                head = head->next; //将头结点指向后继结点
                delete p; //释放原头结点的内存
            } else { //如果头结点不存在，说明链表为空
                cout << "Empty list!" << endl;
            }
        } else { //删除其他位置的结点
            for (int i = 0; i < pos - 1 && p; i++) {
                p = p->next; //找到前驱结点
            }
            if (p && p->next) { //如果前驱结点和后继结点都存在
                ListNode* q = p->next; //保存后继结点的地址
                p->next = q->next; //将前驱结点的指针域指向后继的后继结点
                delete q; //释放后继结点的内存
            } else { //如果前驱结点或后继结点不存在，说明位置不合法
                cout << "Invalid position!" << endl;
            }
        }
    }
    void print() { //遍历链表并打印数据域的值
        ListNode* p = head;
        while (p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};
